package com.lx.algorithm.code;

/**
 * Description:
 * Copyright:   Copyright (c)2019
 * Company:     zefu
 *
 * @author: 张李鑫
 * @version: 1.0
 * Create at:   2021-12-30 11:54:18
 * <p>
 * Modification History:
 * Date         Author      Version     Description
 * ------------------------------------------------------------------
 * 2021-12-30     张李鑫                     1.0         1.0 Version
 */
public class Code05 {
    /**
     * 给定一个N*N的矩阵matrix，只有0和1两种值，返回边框全是1的最大正方形的边长长度。
     * 例如:
     * 01111
     * 01001
     * 01001
     * 01111
     * 01011
     * 其中边框全是1的最大正方形的大小为4*4，所以返回4。
     */

    /**
     * 构建两个二维数组 存储右边跟下面有几个连续的1
     *
     * @param matrix
     * @return
     */
    public static void builder(int[][] matrix, int[][] d, int[][] r) {
        //准备两个数组 一个存储下方有几个连续的1 右边有几个连续的1
        for (int i = 0; i < matrix.length; i++) {
            r[i][matrix[i].length - 1] = matrix[i][matrix[i].length - 1];
            for (int i1 = matrix[i].length - 2; i1 >= 0; i1--) {
                r[i][i1] = matrix[i][i1] == 0 ? 0 : r[i][i1 + 1] + 1;
            }
        }
        for (int i = 0; i < matrix[0].length; i++) {
            d[matrix.length - 1][i] = matrix[matrix.length - 1][i];
        }

        for (int i = matrix.length - 2; i >= 0; i--) {
            for (int i1 = 0; i1 <= matrix[i].length - 1; i1++) {
                d[i][i1] = matrix[i][i1] == 0 ? 0 : d[i + 1][i1] + 1;
            }
        }

    }

    public static int maxOneBorderSize(int[][] matrix) {
        int[][] d = new int[matrix.length][matrix[0].length];
        int[][] r = new int[matrix.length][matrix[0].length];
        int max = 0;
        //构造数组
        builder(matrix, d, r);

        for (int i = 0; i < d.length; i++) {
            for (int i1 = 0; i1 < d[i].length; i1++) {
                //先找到最小的点 然后去校验 如果存在就记录最大数
                int min = Math.min(d[i][i1], r[i][i1]);
                if (min > max && i1 + min-1 < d[i].length && i + min-1 < d.length && d[i][i1 + min-1] >= min && r[i + min-1][i1] >= min) {
                    max = min;
                }
            }
        }
        return max;
    }


}
